\documentclass[a4paper,10pt]{article}
\usepackage[paper=a4paper, hmargin=1.5cm, bottom=1.5cm, top=3.5cm]{geometry}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[spanish]{babel}
\usepackage{xspace}
\usepackage{xargs}
\usepackage{ifthen}
\usepackage{aed2-tad,aed2-symb,aed2-itef}
\usepackage[spanish]{babel} % para escribir en espanol
\usepackage[latin1]{inputenc} % para acentos sin codigo
\usepackage{graphicx} % graficos
\usepackage{multirow, array} % para las tablas
\usepackage{float} % para usar [H]

\usepackage{algorithm}
\usepackage{algpseudocode}

\newcommand{\moduloNombre}[1]{\textbf{#1}}

\let\NombreFuncion=\textsc
\let\TipoVariable=\texttt
\let\ModificadorArgumento=\textbf
\newcommand{\res}{$res$\xspace}
\newcommand{\tab}{\hspace*{7mm}}
\newcommand{\asignacion}{$\leftarrow$}
\newcommand{\retorno}{$\rightarrow$}

\newcommandx{\TipoFuncion}[3]{%
  \NombreFuncion{#1}(#2) \ifx#3\empty\else $\to$ \res\,: \TipoVariable{#3}\fi%
}
\newcommand{\In}[2]{\ModificadorArgumento{in} \ensuremath{#1}\,: \TipoVariable{#2}\xspace}
\newcommand{\Out}[2]{\ModificadorArgumento{out} \ensuremath{#1}\,: \TipoVariable{#2}\xspace}
\newcommand{\Inout}[2]{\ModificadorArgumento{in/out} \ensuremath{#1}\,: \TipoVariable{#2}\xspace}
\newcommand{\Aplicar}[2]{\NombreFuncion{#1}(#2)}

\newlength{\IntFuncionLengthA}
\newlength{\IntFuncionLengthB}
\newlength{\IntFuncionLengthC}
%InterfazFuncion(nombre, argumentos, valor retorno, precondicion, postcondicion, complejidad, descripcion, aliasing)
\newcommandx{\InterfazFuncion}[9][4=true,6,7,8,9]{%
  \hangindent=\parindent
  \TipoFuncion{#1}{#2}{#3}\\%
  \textbf{Pre} $\equiv$ \{#4\}\\%
  \textbf{Post} $\equiv$ \{#5\}%
  \ifx#6\empty\else\\\textbf{Complejidad:} #6\fi%
  \ifx#7\empty\else\\\textbf{Descripci\'on:} #7\fi%
  \ifx#8\empty\else\\\textbf{Aliasing:} #8\fi%
  \ifx#9\empty\else\\\textbf{Requiere:} #9\fi%
}

\newenvironment{Interfaz}{%
  \parskip=2ex%
  \noindent\textbf{\Large Interfaz}%
  \par%
}{}

\newenvironment{Representacion}{%
  \vspace*{2ex}%
  \noindent\textbf{\Large Representaci�n}%
  \vspace*{2ex}%
}{}

\newenvironment{Algoritmos}{%
  \vspace*{2ex}%
  \noindent\textbf{\Large Algoritmos}%
  \vspace*{2ex}%
}{}


\newcommand{\Titulo}[1]{
  \vspace*{1ex}\par\noindent\textbf{\large #1}\par
}

\newenvironmentx{Estructura}[2][2={estr}]{%
  \par\vspace*{2ex}%
  \TipoVariable{#1} \textbf{se representa con} \TipoVariable{#2}%
  \par\vspace*{1ex}%
}{%
  \par\vspace*{2ex}%
}%

\newboolean{EstructuraHayItems}
\newlength{\lenTupla}
\newenvironmentx{Tupla}[1][1={estr}]{%
    \settowidth{\lenTupla}{\hspace*{3mm}donde \TipoVariable{#1} es \TipoVariable{tupla}$($}%
    \addtolength{\lenTupla}{\parindent}%
    \hspace*{3mm}donde \TipoVariable{#1} es \TipoVariable{tupla}$($%
    \begin{minipage}[t]{\linewidth-\lenTupla}%
    \setboolean{EstructuraHayItems}{false}%
}{%
    $)$%
    \end{minipage}
}

\newcommandx{\tupItem}[3][1={\ }]{%
    %\hspace*{3mm}%
    \ifthenelse{\boolean{EstructuraHayItems}}{%
        ,#1%
    }{}%
    \emph{#2}: \TipoVariable{#3}%
    \setboolean{EstructuraHayItems}{true}%
}

\newcommandx{\RepFc}[3][1={estr},2={e}]{%
  \tadOperacion{Rep}{#1}{bool}{}%
  \tadAxioma{Rep($#2$)}{#3}%
}%

\newcommandx{\RepFuncion}[6][]{
  \tadOperacion{#1}{#2}{#3}{#4}
  \tadAxioma{#1(#5)}{#6}
}%

\newcommandx{\Rep}[3][1={estr},2={e}]{%
  \tadOperacion{Rep}{#1}{bool}{}%
  \tadAxioma{Rep($#2$)}{true \ssi #3}%
}%

\newcommandx{\Abs}[5][1={estr},3={e}]{%
  \tadOperacion{Abs}{#1/#3}{#2}{Rep($#3$)}%
  \settominwidth{\hangindent}{Abs($#3$) \igobs #4: #2 $\mid$ }%
  \addtolength{\hangindent}{\parindent}%
  Abs($#3$) \igobs #4: #2 $\mid$ #5%
}%

\newcommandx{\AbsFc}[4][1={estr},3={e}]{%
  \tadOperacion{Abs}{#1/#3}{#2}{Rep($#3$)}%
  \tadAxioma{Abs($#3$)}{#4}%
}%


\newcommand{\DRef}{\ensuremath{\rightarrow}}

\begin{document}

\tableofcontents

\newpage

\section{M\'odulo SADAIC:}

\subsection{Interfaz}

\begin{Interfaz}
	\textbf{se explica con}: \tadNombre{SADAIC}
	\newline
	\textbf{usa}: \tadNombre{String}, \tadNombre{Diccionario Extendido},
	\tadNombre{Conjunto ($\alpha)$}
	\newline
	\textbf{g\'eneros}: \TipoVariable{sadaic}
	\Titulo{Operaciones b\'asicas de Diccionario Extendido:}
	
	\InterfazFuncion{iIniciar}{\In{as}{conj(autor)}}{sadaic}
	[$\neg \emptyset?(as)$]
	{$res \igobs iniciar$}%
	[$O(\sum_{a \in as} long(a))$]
	[Inicia un nuevo sistema SADAIC, definiendo los autores que contiene el mismo.]
	
	\InterfazFuncion{iNuevoTema}{\Inout{s}{sadaic}, \In{t}{tema},
	\In{as}{conj(autor)}}{} 
	[$s \igobs s_{0} \wedge \neg(t \in temas(s)) \wedge \neg \emptyset?(as)
	\wedge as \subseteq autores(s)$] 
	{$s \igobs nuevoTema(s_{0}, t, as)$} 
	[$O(A*long(a) + long(t) + A^2 * T^2 * long(t))$ donde a $\in$
	autores(s) $\wedge$ t $\in$ temas(s)]
	[Agrega un nuevo tema al sistema e indica cuales son los autores de los mismos.]
	
	\InterfazFuncion{iDisputarTema}{\Inout{s}{sadaic}, \In{a}{autor}, \In{t}{tema}}{}
	[$s \igobs s_{0} \wedge t \in temas(s) \wedge a \in autores(s) \wedge \neg(t
	\in temasDe(s, a) \cup temasDisputadosPor(s, a))$] 
	{$s \igobs disputarTema(s_{0}, a, t)$} 
	[$O(long(a) + A * long(t) + A * T * long(t))$]
	[Indica que el autor a disputa el tema t.]
	
	\InterfazFuncion{iTemas}{\In{s}{sadaic}}{itTema}	
	{$res \igobs temas(s)$}
	[$O(1)$]
	[Devuelve los temas que contiene el sadaic.]
	
	\InterfazFuncion{iAutores}{\In{s}{sadaic}}{itAutor}	
	{$res \igobs autores(s)$}
	[$O(1)$]
	[Devuelve los autores que contiene el sadaic.]
	
	\InterfazFuncion{iTemasDe}{\In{s}{sadaic}, \In{a}{autor}}{itTema}
	[$a \in autores(s)$]
	{$res \igobs temasDe(s, a)$}
	[$O(long(a))$]
	[Retorna todos los temas que tiene registrado el autor a.]
	
	\InterfazFuncion{iTemasDisputadosPor}{\In{s}{sadaic},
	\In{a}{autor}}{itTema}
	[$a \in autores(s)$]
	{$res \igobs temasDisputadosPor(s, a)$}	
	[$O(long(a))$]
	[Retorna todos los temas que tiene registrado el autor a.]

	\InterfazFuncion{iCoAutores}{\In{s}{sadaic}, \In{a}{autor}}{itTema}
	[$a \in autores(s)$]
	{$res \igobs coautores(s, a)$}	
	[$O(A * T * (long(a) + A * long(a')))$, en donde $a' \in autores(s)$]
	[Dado un autor, devuelve todos los co autores que tiene dentro del sistema.]
	
	\InterfazFuncion{iTemasNoDisputados}{\In{s}{sadaic}, \In{a}{autor}}{itTema} 
	[$a \in autores(s)$]
	{$res \igobs temasNoDisputados(s, a)$}	
	[$O(long(a))$]
	[Retorna los temas que no tiene en disputas el autor.]
	
	\InterfazFuncion{iFTS}{\In{s}{sadaic}, \In{s}{string}}{itTema} 
	[$a \in autores(s)$]
	{$res \igobs FTS(s, a)$}	
	[$O(A^2 * long(s) * T * long(t) + A * long(s) * T * long(t))$ 
	En donde $t \in temas(t) \wedge (\forall t_{0} : temas(s)) long(s) \geq
	long(t_{0})$]
	[Retorna los temas que no tiene en disputas el autor.]
	
	\InterfazFuncion{iDameUnTemaDisputadoPor}{\Inout{s}{sadaic}, \In{a}{autor}}{tema} 
	[$a \in autores(s)$]
	{$res \igobs dameUnTemaDisputadoPor(s, a)$}	
	[$O(long(a))$]
	[Cuando se invoca el mismo par\'ametro que la llamada anterior, devuelve el
	pr\'oximo tema que tiene disputado el autor, en caso de no ser as\'i, obtiene
	los temas disputados y devuelve el pr\'oximo.]
	
	\subsection{Servicios exportados:}
	\begin{table}[H]
		\centering
		\begin{tabular}{p{10cm} p{8cm}}
			\hline
				Funcion & Complejidad 													\\
			\hline \hline
				iIniciar & $O(\sum_{a \in as} long(a))$ 								\\ 
			\hline
				iNuevoTema & $O(A*long(a) + long(t) + A^2 * T^2 * long(t))$ 			\\
			\hline
				iDisputarTema & $O(long(a) + A * long(t) + A * T * long(t))$ 			\\
			\hline				
				iTemas & $O(1)$ 														\\
			\hline	
				iAutores & $O(1)$ 														\\
			\hline
				iTemasDe & $O(long(a))$ 												\\
			\hline
				iTemasDisputadosPor & $O(long(a))$										\\
			\hline
				iCoAutores & $O(A * T * (long(a) + A * long(a')))$						\\
			\hline
				iFTS$^*$ & $O(A^2 * long(s) * T * long(t) + A * long(s) * T * long(t))$		\\
			\hline	
				iDameUnTemaDisputadoPor & $O(long(a))$									\\
			\hline
			\hline
		\end{tabular}
	\end{table}	
	(*) FTS tiene una complejidad de O(long(s)) cuando el parametro no contiene
	asterisco.
	
	\subsection{Especificaci\'on de las operaciones utilizadas en la interfaz:}
	Se explica con la especificacion dada por la c\'atedra.
	
	\subsection{Estructura de representaci\'on:}
	
 	\begin{table}[H]
		\centering
		\begin{tabular}{p{16cm} p{10cm}}
		\hline
			\begin{Estructura}{SADAIC}[sadaic]
				\begin{Tupla}[sadaic]
					\tupItem{autorXTemas}{diccExtendido(autor, conj(tema))}
					\tupItem{autorXDemandas}{diccExtendido(autor, conj(demanda))}
					\tupItem{autorXNoDemandados}{diccExtendido(autor, conj(demanda))}			
					\tupItem{temaXAutores}{diccExtendido(tema, conj(autor))}			
					\tupItem{autorDisputado}{autor}
					\tupItem{itAutorDisputado}{itTema}
				\end{Tupla}
			\end{Estructura}
		\\
		\hline \hline
		\end{tabular}
	\end{table}
		
	\subsubsection{Explicaci\'on de la estructura elegida}
	Con esta estructura lo que buscamos principalmente es cumplir con los  ordenes
	temporales que nos fueron solicitados en el enunciado del tp. Para esto vamos a 
	necesitar estructuras de soporte que nos permitan cumplir con dichos  ordenes.
	\newline
	\newline
	Para ello vamos a contar con cuatro diccionarios: en uno de los diccionarios
	vamos a guardar como claves los autores que contiene el sistema y como
	significado los temas que el mismo tiene registrado como propios (autorXTemas),
	en un segundo diccionario vamos a almacenar los temas que contiene el sistema,
	como clave, y como significado los autores del mismo.
	\newline
	\newline
	Aparte de estos, vamos a contar con un diccionario para guardar las demandas
	que tiene un autor, as\'i como los temas no demandados que tiene el mismo,
	almacenando como significado temas de su autor\'ia y los de sus co autores.
	\newline
	\newline
	Por \'ultimo, tenemos autorDisputado en donde se guarda el ultimo autor que
	disput\'o un tema y itAutorDisputado contiene un iterador a los temas que tiene
	disputado el autor.
	
	\subsubsection{Invariante de Representaci\'on}
	\textbf{Invariante de representaci\'on informal:}
	\begin{enumerate}
	  \item Todos los temas de \textit{temaXAutores} tienen que estar registrados
	  con al menos un autor.
	  \item Los autores de \textit{temaXAutores} est\'an contenidos en los autores
	  de \textit{autorXTemas}.(redundancia: Como autorXTemas contiene los autores
	  del sistema, es necesario que en temaXAutores tenga todos sus significados
	  con autores v\'alidos.)
	  \item Los temas de \textit{autorXTemas} tienen que estar contenidos dentro
	  los temas de \textit{temaXAutores}.(redundancia: Como temaXAutores contiene
	  todos los temas del sistema, es necesario que en autorXTemas tenga todos
	  sus significados con temas v\'alidos.)
	  \item Los autores en \textit{autorXTemas}, \textit{autorXNoDemandados} y
	  \textit{autorXDemandas} tienen que ser los mismos.(redundancia: Los autores
	  tienen que estar definidos en los tres diccionarios)
	  \item No puede existir un tema que este demandado y no demandado al mismo
	  tiempo. (restricci\'on del TAD: Al momento de demandar un tema no puede
	  estar demandado y al momento de obtener los temas no demandados no puede
	  estar demandado.)
	  \item Los temas en \textit{autorXNoDemandados} y \textit{autorXDemandas}
	  tiene que estar contenidos dentro de \textit{temaXAutores}. (redundancia:
	  Los temas tienen que ser v\'alidos, para eso tiene que estar definido.)
	  \item Dado un autor, los temas que contiene en \textit{autorXDemandas},
	  cumple la siguiente relaci\'on: al tomar cada uno de estos temas y obtener
	  los autores en \textit{temaXAutores}, no puede tener el autor que se
	  utiliz\'o para buscar el significado en \textit{autorXDemandas}.
	  (restricci\'on del TAD: un autor no puede demandarse a s\'i mismo.)
	  \item Dado un autor, los temas que contiene en \textit{autorXTemas}  cumplen
	  la siguiente relaci\'on: al tomar cada uno de esos temas y obtener los
	  autores en \textit{temaXAutores}, el autor que se utiliz\'o tiene que estar
	  dentro de este conjunto.	  
	  (redundancia: hay una relacion entre autor por tema y tema por autor, a parte de ser
	  v\'alidos las claves y los significados, tiene que haber una relaci\'on
	  entre ambas)
	  \item Dado un tema, los autores que contiene en \textit{temaXAutores} cumplen
	  la siguiente relaci\'on: al tomar cada uno de esos autores y obtener sus
	  temas en \textit{autorXTemas}, el tema que se utiliz\'o tiene que estar
	  contenido en este conjunto.
	  \item Dado un autor, los temas que contiene en \textit{autorXNoDemandados} o
	  son temas de su autoria o son temas de sus co autores. (restricci\'on del
	  TAD: los temas que no son demandados, tiene que ser o propios del autor o de
	  sus co autores.)	 
	  \item El \textit{autorDisputado} tiene que ser un autor v\'alido.
	  \item Los temas de \textit{itAutorDisputado} tiene que ser temas disputados
	  del autor \textit{autorDisputado}.
	\end{enumerate}
	
	\textbf{Invariante de representaci\'on formal:}
	
	\Rep[sadaic]{$
	\\(1)\\
	(\forall t : tema), t \in claves(e.temaXAutores) \wedge_{L} \neg
	\emptyset(obtener(t, obtener(temaXAutores))
	
	\\\wedge 
	\\(2)\\
	(\forall t : tema), t \in claves(e.temaXAutores) \wedge_{L}
	obtener(t,e.temaXAutores) \subseteq claves(e.autorXTemas)
	 
	\\\wedge
	\\(3)\\
	(\forall a : autor), a \in claves(e.autorXTemas) \wedge_{L} obtener(a,
	autorXTemas) \subseteq claves(e.temaXAutores)
	
	\\\wedge
	\\(4)\\
	claves(e.autorXTemas) = claves(e.autorXNoDemandados) = claves(e.autorXDemandas)
	
	\\\wedge
	\\(5)\\
	(\forall a_1, a_2 : autor)a_1, a_2 \in claves(e.autorXNoDemandados)
	\wedge_{L} obtener(a_1, e.autorXNoDemandados) \cap obtener(a_2,
	e.autorXDemandas) = \emptyset
	 
	\\\wedge
	\\(6)\\
	(\forall a_1 : autor) a_1 \in claves(e.autorXNoDemandados) \wedge_{L}
	obtener(a_1, e.autorXNoDemandados) \subseteq claves(e.temaXAutores)
	\\
	\wedge
	\\
	(\forall a_2 : autor) a_2 \in claves(e.autorXDemandas) \wedge_{L}
	obtener(a_2, e.autorXDemandas) \subseteq claves(e.temaXAutores)	
	
	\\\wedge
	\\(7)\\
	(\forall a : autor)(\forall t : tema)(a \in claves(e.autorXDemandas) \wedge_{L}
	t \in obtener(a, e.autorXDemandas)) \wedge_{L} a \notin obtener(t, e.temaXAutores)
	
	\\\wedge
	\\(8)\\
	(\forall a : autor)(\forall t : tema)(a \in claves(e.autorXTemas) \wedge_{L} t
	\in obtener(a, e.autorXTemas)) \wedge_{L} a \in obtener(t, e.temaXAutores)	
	
	\\\wedge
	\\(9)\\
	(\forall t : tema)(\forall a : autor)(t \in claves(e.temaXAutores) \wedge_{L}
	a \in obtener(t, e.autorXtemas)) \wedge_{L} t \in obtener(a, e.autorXTemas)
		
	\\\wedge
	\\(10)\\
	(\forall a : autor) (a \in claves(e.autorXNoDemandados)) \Rightarrow
	((\forall t : tema) (t \in obtener(a, e.autorXNoDemandados))  \Rightarrow t \in
	obtener(a, e.autorXTemas) \vee (\exists  i : autor)(i \in coautores(a,
	e.autorXTemas, claves(e.autorXTemas) - {a}) \wedge t \in obtener(i,
	e.autorXTemas)) )
	
	\\\wedge
	\\(11)\\
	e.autorDisputado \in claves(e.autorXTemas)
	
	\\\wedge
	\\(12)\\
	secuAConjunto(Anteriores(e.itAutorDisputado)) \cup
	secuAConjunto(Siguientes(e.itAutorDisputado)) \subseteq
	obtener(e.autorDisputado, e.autorXDemandas)$}
	
	
	\RepFuncion{coautores}{autor /a,  diccExtendido(autor,
	conj(tema)) /d, conj(autor) /ts}{conj(autor)}{$a \notin ts$} 
	{a, b, ts}
	{\IF\ $\neg \emptyset?(ts)$ THEN
		{\IF\ $obtener(dameUno(ts), d) \cap obtener(a, d) \neq \emptyset$ THEN
			Ag(dameUno(ts), coautores(a, d, sinUno(ts)))
		ELSE
			coautores(a, d, sinUno(ts))
		FI}
	ELSE
		$\emptyset$
	FI}
	
	\RepFuncion{secuAConjunto}{secu(autor) /as}{conj(autor)}{} 
	{as}
	{\IF\ vacia?(as) THEN		
		Ag(prim(as), fin(as))		
	ELSE
		$\emptyset$
	FI}
	
	\subsubsection{Funcion de Abstracci\'on}
	\Abs[sadaic]{sadaic}
	{s}{$temas(s) \igobs claves(e.autorXTemas) \wedge autores(s) \igobs
	claves(e.temaXAutores) \wedge (\forall a autores(s)) temasDe(s, a) \igobs
	obtener(e.temaXAutores, a) \wedge temasDisputadosPor(s, a) \igobs
	obtener(e.autorXDemandas, a)$}
	
	\subsubsection{Representaci\'on del iterador}
	A fines de proporcionar un encapsulamiento apropiado para los elementos
	devueltos por SADAIC, se definen los siguientes iteradores:
	\\
	itTema es un itConj(tema)
	\\
	itAutor es un itConj(autor)
	\\
	En donde aplican todas las propiedades propias sobre el iterador de conjunto.
	La ventaja de este tipo de ``renombre'' es el hecho de que si en un futuro se
	cambia la eleccion del iterador a exponer, solo se debe modificar el renombre
	sin afectar la interfaz proporcionada hacia el usuario.	
\end{Interfaz}

\subsection{Eficiencia de Temas No Disputados:}
En un principio vamos a aclarar en que pensamos cuando vimos el tema de
temasNoDisputados, en un principio vimos lo que había que hacer y empezamos
a correr en círculos dejando una estela de fuego, pero luego lo meditamos 
y pensamos en lo siguiente:
\begin{enumerate}
  \item Voy a armarme un diccionario que dado un autor me devuelva los temas no
  disputados.
  \item Para lograrlo, cada vez que se registre un tema para un autor, lo
  registro tambien en este diccionario, ya que en ese momento el tema no esta
  disputado.
  \item Luego, una vez que se termino de agregar el tema, tomo a todos los
  autores y a cada autor, le pido sus co autores y a cada co autor, le pido sus
  temas y lo agrego como propios.
  \item Cuando se disputa un tema, tomo de este diccionario, todos los autores y
  si existe algun autor que tenga este tema, lo elimino.
\end{enumerate}

De esta forma, en este diccionario, por cada autor, definido como clave, va a
devolver un conjunto de temas como significado, pero no cualquier conjunto de
temas, si lo pensamos como conjunto, este conjunto esta formado por: \{``temas
propios\} $\cup$ \{``temas de mis co autores\} - \{ ``el universo de los temas
demandados"\}. Entonces cuando consulto por un autor como clave, voy a tener la
informaci\'on que necesito en un costo de O(long(a)) ya que la implementaci\'on
es eficiente en el momento de accederlo. El único tema de debate fue el hecho de
agregar un diccionario mas a la estructura, pero si lo queríamos de manera
eficiente al lado, no teníamos de otra forma.
\newline
\newline
Ahora, seg\'un lo pedido, vamos a dar otra alternativa de c\'omo obtener la
misma informaci\'on, la ventaja es que en este punto uno puede hacer un
desastre, total busco algo menos eficiente:
\newline
\newline
\begin{algorithmic}
	\State conj(tema) resultado \asignacion Vacio()
	\\
	\Comment{Lo primero que voy a fijarme es los temas que no tienen demandados el
	autor pasado por parametro} 
	\State itConj(tema) itTemas \asignacion iObtener(s.autorXTemas, a)	  
	\State bool estaDemandado \asignacion false
	
	\While{HaySiguiente(itTemas)}
		\State estaDemandado \asignacion false
		\State string tema \asignacion Siguiente(itTemas) 
		\State itConj(autor) itAutorDemanda \asignacion iClaves(s.autorXDemandas)
		\\
		\Comment{Voy a tomar los autores que realizaron demandas y voy a fijarme si
		alguno de ellos tienen algun tema demandado que coincide con el tema actual}
		\While{HaySiguiente(itAutorDemanda)}
			\State string autor \asignacion Siguiente(itAutorDemanda)
			\State itConj(tema) itTemaDemandado \asignacion iObtener(s.autorXDemandas, autor)
			\While{HaySiguiente(autorXDemandas)}
				\State string temaDemandado \asignacion Siguiente(autorXDemandas)
				\If{temaDemandado = tema}
					\State estaDemandado \asignacion true			
				\EndIf
				\State Avanzar(itAutorDemanda)
			\EndWhile
			\State Avanzar(itAutorDemanda)
		\EndWhile
		\Comment{Si no hubo ninguna demanda, me lo quedo}
		\If{$\neg estaDemandado$}
			\State Agregar(resultado, tema)
		\EndIf
		\State Siguiente(itTemas)
	\EndWhile
	
	\Comment{Ahora voy a tener que repetir el mismo proceso para los co autores.}
	\State itConj(autor) itCoAutores \asignacion iCoAutores(s, a)
	\While{HaySiguiente(itCoAutores)}
		\State coautor \asignacion Siguiente(itCoAutores)
		
		\State itConj(tema) itTemas \asignacion iObtener(s.autorXTemas, coautor)	  
		\State bool estaDemandado \asignacion false
		
		\While{HaySiguiente(itTemas)}
			\State estaDemandado \asignacion false
			\State string tema \asignacion Siguiente(itTemas) 
			\State itConj(autor) itAutorDemanda \asignacion iClaves(s.autorXDemandas)
			\\
			\Comment{Voy a tomar los autores que realizaron demandas y voy a fijarme si
			alguno de ellos tienen algun tema demandado que coincide con el tema actual}
			\While{HaySiguiente(itAutorDemanda)}
				\State string autor \asignacion Siguiente(itAutorDemanda)
				\State itConj(tema) itTemaDemandado \asignacion iObtener(s.autorXDemandas, autor)
				\While{HaySiguiente(autorXDemandas)}
					\State string temaDemandado \asignacion Siguiente(autorXDemandas)
					\If{temaDemandado = tema}
						\State estaDemandado \asignacion true			
					\EndIf
					\State Avanzar(itAutorDemanda)
				\EndWhile
				\State Avanzar(itAutorDemanda)
			\EndWhile
			\Comment{Si no hubo ninguna demanda, me lo quedo}
			\If{$\neg estaDemandado$}
				\State Agregar(resultado, tema)
			\EndIf
			\State Siguiente(itTemas)
		\EndWhile
		\State Avanzar(itCoAutores)
	\EndWhile	
\end{algorithmic}

Entonces, en esta alternativa tenemos que realizar varias iteraciones y a eso
agregando que ni siquiera estamos utilizando el AgregarRapido de conjunto de
resultado, sino que estamos utilizando el Agregar que hace el proceso aun mas
lento.

\subsection{Algoritmos modulo SADAIC:}

\subsubsection{iIniciar:}

\begin{algorithm}
	\begin{algorithmic}[1]
		\State res.autorXTemas \asignacion iVacio()
		\State res.autorXDemandas \asignacion iVacio()
		\State res.temaXAutores \asignacion iVacio()		
		\State res.autorXNoDemandados \asignacion iVacio()
		
		\State conj(string) itAutor \asignacion CrearIt(as)
		\While{HaySiguiente(itAutor)}
			\State string autor \asignacion Siguiente(itAutor)
			\State iDefinir(res.autorXTemas, autor, Vacio())
			\State iDefinir(res.autorXDemandas, autor, Vacio())
			\State iDefinir(res.autorXNoDemandados, autor, Vacio())
			\State Avanzar(itAutor)
		\EndWhile
	\end{algorithmic}
	\caption{iIniciar(in as :conj(autor)) \retorno res :sadaic}
\end{algorithm}	

\subsubsection{iNuevoTema:}
\begin{algorithm}
	\begin{algorithmic}[1]
		\State iDefinir(s.temaXAutores, t, as)
		\State itConj(string) itAutor \asignacion CrearIt(as)
		\While{HaySiguiente(itAutor)}
			\State string autor \asignacion Siguiente(itAutor)
			\State iAgregarSignificado(s.autorXTemas, autor, t)
			\State iAgregarSignificado(s.autorXNoDemandados, autor, t)				
			\State Avanzar(itAutor)
		\EndWhile
		
		\State itConj(string) itAutores \asignacion iClaves(s.autorXNoDemandados)
		\While{HaySiguiente(itAutores)}
			\State string autor \asignacion Siguiente(itAutores)
			\State itConj(string) itCoAutores \asignacion iCoAutores(s, autor)
			\While{HaySiguiente(itCoAutores)}
				\State string coautor \asignacion Siguiente(itCoAutores)
				\State itConj(string) itTemas \asignacion iObtener(s.autorXTemas, coautor)
				\While{HaySiguiente(itTemas)}
					\State string tema \asignacion Siguiente(itTemas)
					\State iAgregarSignificados(s.autorXNoDemandados, autor, tema)
					\State Avanzar(itTemas)
				\EndWhile
				\State Avanzar(itCoAutores)
			\EndWhile
			\State Avanzar(itAutores)
		\EndWhile 
	\end{algorithmic}
	\caption{iNuevoTema(in/out s sadaic, in t tema, in as conj(autor))}
\end{algorithm}

\subsubsection{iDisputarTema:}
\begin{algorithm}
	\begin{algorithmic}[1]
		\State iAgregarSignificado(s.autorXDemandas, a, t)
		\State itConj(string) itAutores \asignacion iClaves(s.autorXNoDemandados)
		\While{HaySiguiente(itAutores)}
			\State string autor \asignacion Siguiente(itAutores)
			\State itConj(string) itNoDemandados \asignacion iObtener(s.autorXNoDemandados, autor)
			\While{HaySiguiente(itNoDemandados)}
				\State string noDemandado \asignacion Siguiente(itNoDemandados)
				\If{noDemandado = t}
					\State Retroceder(itNoDemandados)
					\State EliminarSiguiente(itNoDemandados)
				\EndIf
				\State Avanzar(itNoDemandados)
			\EndWhile	
			\State Avanzar(itAutores)
		\EndWhile
	\end{algorithmic}
	\caption{iDisputarTema(in/out s sadaic, in a autor, in t tema)}
\end{algorithm}	

\clearpage

\subsubsection{iTemas:}
\begin{algorithm}
	\begin{algorithmic}[1]
		\State res \asignacion iClaves(s.temaXAutores)	
	\end{algorithmic}
	\caption{iTemas(in s sadaic) \retorno itTema}
\end{algorithm}

\subsubsection{iAutores:}
\begin{algorithm}
	\begin{algorithmic}[1]
		\State res \asignacion iClaves(s.autorXTemas)	
	\end{algorithmic}
	\caption{iAutores(in s sadaic) \retorno res :itAutor}
\end{algorithm}

\subsubsection{iTemasDe:}
\begin{algorithm}
	\begin{algorithmic}[1]			
		\State res \asignacion iObtener(s.autorXTemas, a)						
	\end{algorithmic}
	\caption{iTemasDe(in s sadaic, in a autor) \retorno itTema}
\end{algorithm}	

\clearpage

\subsubsection{iTemasDisputadosPor:}
\begin{algorithm}
	\begin{algorithmic}[1]
		\State res \asignacion iObtener(s.autorXDemandas, a)
	\end{algorithmic}
	\caption{iTemasDisputadosPor(in s sadaic, in a autor) \retorno itTema}
\end{algorithm}

\subsubsection{iCoAutores:}
\begin{algorithm}
	\begin{algorithmic}[1]
		\State conj(string) autores \asignacion Vacio()
		\State itConj(string) itTemas \asignacion iObtener(s.autorXTemas, a)
		\While{HaySiguiente(itTemas)}
			\State string tema \asignacion Siguiente(itTemas)
			\State itConj(string) itAutores \asignacion iObtener(s.temaXAutores, tema)
			\While{HaySiguiente(itAutores)}
				\State string autor \asignacion Siguiente(itAutores)
				\If {$\neg (a = autor)$}
					\State Agregar(autores, autor)
				\EndIf
				\State Avanzar(itAutores)
			\EndWhile
			\State Avanzar(itTemas)
		\EndWhile
		\State res \asignacion CrearIt(autores)
	\end{algorithmic}
	\caption{iCoAutores(in s sadaic, in a autor) \retorno itTema}
\end{algorithm}

\subsubsection{iTemasNoDisputados:}
\begin{algorithm}
	\begin{algorithmic}[1]		
		\State res \asignacion CrearIt(iObtener(s.autorXNoDemandados))
	\end{algorithmic}
	\caption{iTemasNoDisputados(in s sadaic, in a string) \retorno itTema}
\end{algorithm}

\clearpage

\subsubsection{iFTS:}
\begin{algorithm}
	\begin{algorithmic}[1]
		\State conj(string) busqueda \asignacion Vacio()				
		\If{iDef?(s.autorXTemas, s)}
			\Comment{Si se encuentra definido dentro del diccionario de autores, solo
			debo devolver los temas de este.}
			\State res \asignacion iObtener(s.autorXTemas, s)			
		\ElsIf{iDef?(s.temaXAutores, s)}
			\Comment{Si se encuentra definido dentro del diccionario de temas, solo
			devuelvo el tema, ya que significa que coloco el nombre del tema}
			\State AgregarRapido(busqueda, s)
			\State res \asignacion CrearIt(busqueda)
		\Else
			\Comment{Si no estoy en los dos casos anteriores, significa que debe ser una
			expresion}			
			\State itConj(string) itAutores \asignacion iObtenerSignificados(s.autorXTemas, s)
			\While{HaySiguiente(itAutores)}
				\State string autor \asignacion Siguiente(itAutores)
				\State AgregarRapido(busqueda, autor)
				\State Avanzar(itAutores)
			\EndWhile			
			
			\State itConj(string) itTema \asignacion iClavesCoincidentes(s.temaXAutores, s)
			\While{HaySiguiente(itTema)}
				\State string tema \asignacion Siguiente(itTema)
				\State Agregar(busqueda, tema)
				\State Avanzar(itTema)
			\EndWhile
			\State res \asignacion CrearIt(busqueda)
		\EndIf
	\end{algorithmic}
	\caption{iFTS(in s sadaic, in s string) \retorno itTema}
\end{algorithm}

\subsubsection{iDameUnTemaDisputadoPor:}
\begin{algorithm}
	\begin{algorithmic}[1]
		\If{$\neg (s = s.autorDisputado)$}			 
			\State s.itAutorDisputado \asignacion iObtener(s.autorXDemandas, s)
		\EndIf		
		\State Siguiente(s.itAutorDisputado)
	\end{algorithmic}
	\caption{iDameUnTemaDisputadoPor(in s sadaic, in a string) \retorno tema}
\end{algorithm}
	
\newpage

\section{M\'odulo Diccionario Extendido:}
El m\'odulo diccionario extendido provee un diccionario con el agregado de
algunas propiedades, las operaciones de definir, obtener, y testear si una 
clave est\'a definida en tiempo proporcional a la longitud de la clave a operar. 
\newline
\newline
Cuando la clave ya se encuentra definida, se puede agregar un significado en 
tiempo proporcional a la longitud de la clave.
\newline
\newline
En cuanto al recorrido de los datos, se provee un iterador bidireccional que 
permite recorrer los elementos, pero no permite eliminar los elementos devueltos 
ni alterar los elementos devueltos.
\newline
\newline
Para describir la complejidad de las operaciones, vamos a llamar a
equals($k_{1}$, $k_{2})$ al costo de evaluar si dos elementos , $k_{1}$ y
$k_{2}$ son iguales.

\subsection{Interfaz}

\begin{Interfaz}
	\textbf{se explica con}: \tadNombre{Diccionario Extendido}
	\\
	\textbf{g\'eneros}: \TipoVariable{diccExtendido}
	
	\Titulo{Operaciones b\'asicas de Diccionario Extendido:}

	\InterfazFuncion{iVac\'io}{}{diccExtendido}
  	{$res \igobs vacio$}%
  	[$O(1)$]
  	[Genera un diccionario vac\'io]
  	
	\InterfazFuncion{iDefinir}{\Inout{d}{diccExtendido},
	\In{c}{string}, \In{s}{conj(string)}}{} 
	[$d \igobs d_{0} \wedge \neg (c \in claves(d))$]
	{$d \igobs definir(c, s, d_{0})$} 
	[$O(long(c))$]
	[Define la clave c con el significado s en el diccionario extendido.] 
	[Los elementos se definen por referencia.]
	
	\InterfazFuncion{iAgregarSignificado}{\Inout{d}{diccExtendido},
	\In{c}{string}, \In{s}{string}}{} 
	[$d \igobs d_{0} \wedge (def?(d, c) \wedge_{L} \neg(s \in obtener(d, c)))$]
	{$d \igobs definir(c, s, d_{0})$} 
	[$O(long(c) + long(s))$]
	[Define la clave c con el significado s en el diccionario extendido.] 
	[Los elementos se definen por referencia.]	
	
	\InterfazFuncion{iDef?}{\In{d}{diccExtendido}, \In{c}{string}}{boolean}
	{$d \igobs def?(c, d)$}
	[$O(long(c))$]
	[Devuelve true si y s\'olo si c est\'a definido en el diccionario extendido.]
	
	\InterfazFuncion{iClaves}{\In{d}{diccExtendido}}{itConj(string)}	
	{$res \igobs claves(d)$}
	[$O(1)$]
	[Retorna las claves definidas dentro del diccionario extendido. El iterador no
	permite realizar modificacion alguna sobre el conjunto original.]
	
	\InterfazFuncion{iObtener}{\In{d}{diccExtendido}, \In{c}{string}}{itConj(string)}
	[def?(c,d)]
	{$res \igobs significado(c, d)$}
	[O(long(c))]
	[Retorna el significado de la clave k en d. Los significados se pasan mediante
	un iterador que no permite realizar ninguna modificacion sobre el conjunto
	original.]
	
	\InterfazFuncion{iObtenerSignificados}{\In{d}{diccExtendido}, \In{c}{string}}{itConj(string)} 
	{$res \igobs obtenerSignificados(c, d)$}	
	[$O(\#claves(d) * long(c) * \#claves(d) * \#claves(d) * long(s))$, en donde $s
	\in significados(d) \wedge (\forall e \in significados(s)), long(s) \geq
	long(e)$]
	[Retorna todos los significados cuyas claves cumplen con
	la condicion que c sea prefijo de las mismas.]
	
	\InterfazFuncion{iCoincide}{\In{d}{string}, \In{c}{string}}{bool} 
	{$res \igobs coincide(d, c)$}
	[O(long(d))]
	[Indica si el string d coincide con el string c.]
	
	\InterfazFuncion{iClavesCoincidentes}{\In{s}{string}, \In{cs}{conj(string)}}{conj(string)} 
	{$res \igobs clavesCoincidentes(d, cs)$}
	[$O(\#cs* long(s))$]
	[Devuelve todas las claves que coinciden con s]
	
	
	\subsection{Servicios exportados:}
	\begin{table}[H]
		\centering
		\begin{tabular}{p{10cm} p{8cm}}
			\hline
				Funci\'on & Complejidad 												\\
			\hline \hline
				iVac\'io & $O(1)$						 								\\ 
			\hline
				iDefinir & $O(A * long(a) + A^2 * long(t) + A^2 * T^2 * long(t))$ 		\\
			\hline
				iAgregarSignificado & $long(c) + long(s)$				\\
			\hline				
				iDef? & $O(long(c))$													\\
			\hline	
				iClaves & $O(1)$														\\
			\hline
				iObtener & $O(long(c))$													\\
			\hline			
			\hline
		\end{tabular}
	\end{table}	
	
	\subsection{Especificaci\'on de las operaciones utilizadas en la interfaz:}
	\begin{tad}{\tadNombre{Diccionario Extendido}}
		\tadGeneros{diccExtendido}
		\tadExtiende{Diccionario(String, Conj(String))}
		
		\tadOtrasOperaciones
		\tadOperacion{agregarSignificado}{string /c, string /s, diccExtendido /d}{diccExtendido} 
		{$def?(c, d) \wedge_{L} \neg(s \in obtener(d, c))$} 
		
		\tadOperacion{obtenerSignificados}{String /s, diccExtendido /d}{conj(String)}
		{}
		
		\tadOperacion{obtenerConjuntos}{conj(String) /cs, diccExtendido /d}{conj(String)} 
		{$cs \subseteq claves(d)$}
		
		\tadOperacion{clavesCoincidentes}{String /s, conj(String) /cs}{conj(String)} 
		{$cs \subseteq claves(d)$}
				
		\tadAxiomas[\paratodo{String}{c,s}, \paratodo{Conj(String)}{cs}, \paratodo{DiccExtendido}{d}]
		\tadAxioma{agregarSignificado(c, s, d)}{Ag(d, obtener(c, d))}		
		
		\tadAxioma{obtenerSubClave(s, d)}{obtenerConjuntos(clavesCoincidentes(s, claves(d)), d)}
		
		\tadAxioma{obtenerConjuntos(cs, d)}
		{\IF\ $\neg \emptyset?(cs)$ THEN
			$obtener(dameUno(cs), d) \cup obtenerConjuntos(sinUno(cs), d)$ 
		ELSE
			$\emptyset$
		FI}
		
		\tadAxioma{clavesCoincidentes(s, cs)}
		{\IF\ $\neg \emptyset?(cs)$ THEN
			{\IF\ $coincide(s, dameUno(cs))$ THEN
				Ag(dameUno(cs), clavesCoincidentes(sinUno(cs), s))
			ELSE
				clavesCoincidentes(sinUno(cs), s)
			FI}
		ELSE
			$\emptyset$
		FI}		
	\end{tad}
	
	\subsection{Estructura de representaci\'on:}
	 \begin{table}[H]
		\centering
		\begin{tabular}{p{16cm} p{10cm}}
		\hline
			\begin{Estructura}{Diccionario Extendido}[diccExtendido]
				\begin{Tupla}[diccExtendido]
					\tupItem{raiz}{puntero(Nodo)}
					\tupItem{claves}{conj(string)}			
				\end{Tupla}
				\begin{Tupla}[Nodo]
					\tupItem{significado}{conj(string)>)}
					\tupItem{hojas}{arreglo\_estatico de puntero(Nodo) [256]}
				\end{Tupla}
			\end{Estructura}
		\\
		\hline \hline
		\end{tabular}
	\end{table}	
	
	\subsubsection{Explicaci\'on de la estructura elegida}
	La representaci\'on por la cual hemos optado consiste en definir al diccionario
	como un puntero hacia su nodo principal el cual est\'a definido como: los
	elementos que contiene en relaci\'on a la informaci\'on que debe contener hasta
	ese prefijo y un arreglo est\'tico el cual define (en cada sub\'ndice) una
	letra del alfabeto.

	
	\subsubsection{Invariante de Representaci\'on}
	\textbf{Invariante de representaci\'on informal:}
	\begin{enumerate}
	  \item Cada una de las claves guardadas en claves, deber\'a estar definida en la
	  ra\'iz.
	  \item Debemos asegurar que el un nodo dentro del \'arbol no apunta a su ra\'iz de
	  nuevo.
	  \item Verificar que un mismo nodo no tenga dos padres.
	\end{enumerate}
	
	\textbf{Invariante de representaci\'on formal:}
		
	\Rep[diccExtendido]{$\forall(c : e.claves) def?(c, d.raiz) \wedge
	\forall(s, t : Nodo)(contieneNodo(d.raiz, s) \wedge contieneNodo(d.raiz, t))
	\wedge_{L} ((hayCamino?(s, t) \wedge \neg hayCamino?(t, s)) \wedge \neg
	compartenHijos(a, b))$}
	
	\RepFuncion{contieneNodo}{puntero(Nodo) /raiz, nodo /Nodo}{boolean}{}
	{raiz, nodo}
	{$\neg (raiz == NULL) \wedge_{L} (*(raiz) = nodo \cup (\exists \alpha \in
	A^*)contieneNodo(*(raiz).hojas[\alpha], nodo))$}
	
	\RepFuncion{hayCamino?}{Nodo /a, Nodo /b}{boolean}{$a \neq b$}
	{a, b}
	{$(\exists \alpha \in A^*)contieneNodo(b.hojas[\alpha], a)$}
	
	\RepFuncion{compartenHijos}{Nodo /a, Nodo /b}{boolean}{$a \neq b$}
	{a, b}
	{$(\exists \alpha \in A^*) *(a.hojas[\alpha]) =  *(b.hojas[\alpha])$}
	
	\subsubsection{Funci\'on de Abstracci\'on}
	
	\Abs[diccExtendido]{diccExtendido}{d}{$((\forall s :
	string) def?(c, d) \leftrightarrow c \in e.claves) \wedge_{L} (\forall c :
	claves(d))obtener(c, d) = obtener(c, e.raiz)$}
	
	\RepFuncion{def?}{puntero(Nodo) /raiz, string /clave}{boolean}{}
	{raiz, clave}
	{\IF\ $ \neg vacia?(clave) \wedge raiz != NULL$ THEN
		def?(*(raiz).hojas[prim(clave)], fin(clave))
	ELSE
		$\neg vacia?(clave) \wedge_{L} \neg \emptyset(*(raiz).significado)$
	FI}

	\RepFuncion{obtener}{puntero(Nodo) /raiz, string /clave}{conj(string)}
	{def?(raiz, clave)}
	{raiz, clave}
	{\IF\ $ \neg vacia?(clave)$ THEN
		obtener(*(raiz).hojas[prim(clave)], fin(clave))
	ELSE
		$*(raiz).significado$
	FI}	
\end{Interfaz}

\subsection{Algoritmos modulo Diccionario Extendido:}

\subsubsection{iVacio:}

\begin{algorithm}
	\begin{algorithmic}[1]
		\State res.raiz \asignacion \&(iNuevoNodo())		
		\State res.claves \asignacion Vacio()
	\end{algorithmic}
	\caption{iVacio() \retorno res :diccExtendido}\label{alg:iVacio}
\end{algorithm}

\subsubsection{iNuevoNodo:}

\begin{algorithm}
	\begin{algorithmic}[1]
		\State res.significado \asignacion Vacio()		
		\State int i \asignacion 0
		\While{$i < 256$}
			\State res.hojas[i] \asignacion NULL
			\State i \asignacion i + 1
		\EndWhile		
	\end{algorithmic}
	\caption{iNuevoNodo()\retorno res :Nodo}\label{alg:iNuevoNodo}
\end{algorithm}

\subsubsection{iDefinir:}

\begin{algorithm}
	\begin{algorithmic}[1]					
		\State AgregaRapido(d.claves, c)		
		\State itUni(char) itC \asignacion crearItUni(c)
		\State puntero(Nodo) trie \asignacion d.raiz		
		
		\While{$HayMas?(itC)$}
			\State char hoja \asignacion Actual(itC)			
			\State trie \asignacion *(trie).hojas[hoja]			
			\If{trie == NULL}
				\State trie \asignacion \&(iNuevoNodo())
			\EndIf						
			\State Avanzar(itC)			
		\EndWhile
		\State *(trie).significado \asignacion cs
	\end{algorithmic}
	\caption{iDefinir(in/out d :diccExtendido, in c :string, in cs: conj(string))}	
\end{algorithm}

\clearpage

\subsubsection{iAgregarSignificado:}

\begin{algorithm}
	\begin{algorithmic}[1]		
		\State itUni(char) itC \asignacion crearItUni(c)
		\State puntero(Nodo) trie \asignacion d.raiz
		\While{$HayMas?(itC)$}
			\State char hoja \asignacion Actual(itC)
			\State trie \asignacion *(trie).hojas[hoja]
			\State Avanzar(itC)
		\EndWhile
		\State AgregarRapido(*(trie).significado, s)
	\end{algorithmic}
	\caption{iAgregarSignificado(in/out d :diccExtendido, in c :string, in s: string)}
\end{algorithm}

\subsubsection{iDef?:}

\begin{algorithm}
	\begin{algorithmic}[1]
		\State itUni(char) itC \asignacion CrearItUni(c)
		\State puntero(Nodo) trie \asignacion d.raiz

		\While{$HayMas?(itC) \wedge trie != NULL$}
			\State hoja \asignacion Actual(itC)
			\State trie \asignacion *(trie).hojas[hoja]
			\State Avanzar(itS)
		\EndWhile
		\State $res \leftarrow \neg HayMas?(itS) \wedge_{L} Cardinal(*(trie).significado) != 0$
	\end{algorithmic}
	\caption{iDef?(in d :diccExtendido, in c :string) \retorno res :boolean}
\end{algorithm}

\subsubsection{iClaves:}

\begin{algorithm}
	\begin{algorithmic}[1]
		\State res \asignacion CrearIt(d.claves)
	\end{algorithmic}
	\caption{iClaves(in d :diccExtendido) \retorno res :itConj(string)}
\end{algorithm}

\clearpage

\subsubsection{iObtener:}

\begin{algorithm}
	\begin{algorithmic}[1]
		\State itUni(char) itC \asignacion crearItUni(c)
		\State puntero(Nodo) trie \asignacion d.raiz
		\While{$HayMas?(itC)$}
			\State char hoja \asignacion Actual(itC)
			\State trie \asignacion *(trie).hojas[hoja]
			\State Avanzar(itC)
		\EndWhile
		\State res \asignacion CrearIt(*(trie).significado)		
	\end{algorithmic}
	\caption{iObtener(in d :diccExtendido, in c :string) \retorno res :itConj(string)}
\end{algorithm}

\subsubsection{iObtenerSignificados:}

\begin{algorithm}
	\begin{algorithmic}[1]
		\State conj(string) significados \asignacion Vacio()
		\State itConj(string) itClave \asignacion iClavesCoincidentes(d.claves, c)
		\While{$HaySiguiente(itClave)$}
				\State string clave \asignacion Siguiente(itClave)
				\State itConj(string) itSignificado \asignacion iObtener(d, c)
				\While{$HaySiguiente(itSignificado)$}
					\State string significado \asignacion Siguiente(itSignificado)
					\State Agregar(res, significados)
					\State Avanzar(itSignificado)			
				\EndWhile
			\State Avanzar(itClave)
		\EndWhile
		\State res \asignacion CrearIt(significados)
	\end{algorithmic}
	\caption{iObtenerSignificados(in d :diccExtendido, in c :string) \retorno res :itConj(string)}
\end{algorithm}

\subsubsection{iCoincide:}
\begin{algorithm}
	\begin{algorithmic}[1]
		\State bool res \asignacion true
		\If{long(d) > long(c)}
			\State res \asignacion false
		\Else
			\State itUni(char) itD \asignacion crearItUni(d)
			\State itUni(char) itC \asignacion crearItUni(c)
			\While{$HaySiguiente?(itD) \wedge HaySiguiente?(itC)$}
				\State char caracterD \asignacion Actual(itD)
				\State char caracterC \asignacion Actual(itC)
				\If{$\neg (r = '*')$}
					\State $res \leftarrow res \wedge (caracterD = caracterC)$
				\EndIf
				\State Avanzar(itC)
				\State Avanzar(itD)
			\EndWhile
		\EndIf 
	\end{algorithmic}
	\caption{iCoincide(in d :string, in c :string) \asignacion res :boolean}
\end{algorithm}

\subsubsection{iClavesCoincidentes:}

\begin{algorithm}
	\begin{algorithmic}[1]
		\State itConj(string) itClaves \asignacion CrearIt(iClaves(ds))
		\State conj(string) filtro \asignacion Vacio()
		\While{HaySiguiente(itClaves)}
			\State string clave \asignacion Siguiente(itClaves)
			\If{iCoincide(c, clave)}
				\State AgregarRapido(filtro, clave)
			\EndIf
			\State Avanzar(itClaves)
		\EndWhile
		\State res \asignacion CrearIt(filtro)
	\end{algorithmic}
	\caption{iClavesCoincidentes(in ds :conj(string), in c :string) \retorno res :itConj(string)}
\end{algorithm}

\newpage

\section{Complejidades}

\subsection{Consideraciones}

A continuaci\'on se indicaran, argumentaran y justificaran las complejidades que
tienen los algoritmos que conforman la resoluci\'on del trabajo pr\'actico. A
fines de no tornar demasiado engorroso el proceso de descripci\'on se tendr\'an
en cuenta las siguientes consideraciones:

\begin{enumerate}
  \item Las operaciones de asignacion, acceso a un elemento de un arreglo,
  operaciones sobre un iterador, tienen un costo de O(1)
  \item Los argumentos que se reciben mediante referencia, tienen un costo de
  O(1).
  \item Las operaciones sobre los string tienen un costo lineal, en cuanto a la
  comparacion de dos string, el costo se define como tomar la longitud de uno u
  otro string, ya que en el peor de los casos el costo se obtiene comparando
  todos los elementos de uno de los dos string.
\end{enumerate}

Hechas estas aclaraciones, se busca ir al ``grueso'' de las complejidades,
deteni\'endonos en los detalles m\'as importantes. Es decir aquellas operaciones
que sabemos que tienen un costo de O(1) no entraran en la descripci\'on de los
An\'alisis ya que sabemos que en comparaci\'on con la ejecuci\'on de otras
operaciones van en desmedro.

\subsection{iIniciar}
La complejidad que tiene la funci\'on va a quedar determinada en funci\'on del costo
que tenemos al iterar el ciclo.
\newline
\newline
En cada iteraci\'on, se van definiendo las claves en cada uno de diccionarios
relacionados. La complejidad nos queda como lo siguiente:
\newline
\newline 
$O(\sum_{a \in as}{long(a) + long(a) + long(a)}) \equiv O(\sum_{a \in as}{3 *
long(a)}) \equiv O(\sum_{a \in as}{long(a)})$

\subsection{iNuevoTema}
Para analizar la complejidad de esta funci\'on, la cual da v\'ertigo el solo verla,
vamos a ``partirla'' en dos para su an\'alisis: por un lado vamos a analizar el
primer ciclo en el cual agregamos los significados a dos diccionarios y el
segundo en donde a cada autor agregamos los temas de su co autor.
\newline
\newline
En primer lugar, se agregan los significados a dos diccionarios, por lo tanto
podemos ver la complejidad (de esta primera parte) de la siguiente forma:
\newline
\newline
$O(\sum_{a \in autores(s)}agregarSignificado(s, a, t) +
agregarSignificado(s, a, t)) \equiv
\\
O(\sum_{a \in autores(s)}2 * agregarSignificado(s, a, t)) \equiv 
O(\sum_{a \in autores(s)}agregarSignificado(s, a, t)) \equiv 
\\ 
O(\sum_{a \in autores(s)} long(a) + long(t)) \equiv 
\\
O(\sum_{a \in autores} long(a) + long(t))$
\newline
\newline
Algunas consideraciones sobre la complejidad, en este caso puedo ``sumar'' las
funciones de agregar significado debido a que en ambos casos, definen las mismas
claves pero con distintos significados, como la complejidad depende de la clave
y del significado a agregar a nivel complejidad resulta ser la misma.
\newline
\newline
En segundo t\'ermino nos queda tres bucles anidados para agregar los temas de los
co autores a un autor. Si pensamos las iteraciones como sumatoria de operaciones
sobre conjuntos, nos queda de la siguiente forma:
\newline
\newline
$O(\sum_{a \in autores(s)} \sum_{c \in coautor(s, a)} \sum_{t \in temasDe(s, c)}
\sum_{t_{0} \in temas(s)}equals(t, t_{0}))$
\newline
\newline
Pero hay un detalle que puede hacer que la expresi\'on vuelva a re escribirse,
cuando hablamos de coautores para un autor, puede ser, en el peor de los casos,
todos los autores menos uno (aquel que realiza la consulta), pero si lo pensamos
a nivel de conjunto $coautor \subset autores(s)$ como estamos haciendo una cota
superior para la complejidad, podemos re escribirla de la siguiente manera:
\newline
\newline
$O(\sum_{a \in autores(s)} \sum_{c \in autores(s)} \sum_{t \in temasDe(s, c)}
\sum_{t_{0} \in temas(s)}equals(t, t_{0})) \equiv$
\\
$O(A * A * T * \sum_{t \in temas(s)}long(t)) \equiv O(A^2 * T * \sum_{t \in temas(s)}long(t)) $
\newline
\newline
Quedandonos la complejidad del algoritmo como:
\newline
\newline
$O(\sum_{a \in autores(s)} (long(a) + long(t)) + (A^2 * T * \sum_{t \in
temas(s)}long(t)))$
\newline
\newline
Hay dos expresiones que pueden ``re escribirse'':
\newline
\newline
$O(\sum_{a \in autores(s)} long(a)) \equiv O(A * long(a))$
\newline
Esto es cierto si $a \in autores(s) \wedge (\forall a' \in autores(s)) long(a) \geq long(a')$
\newline
\newline
$O(\sum_{t \in temas(s)}long(t)) \equiv O(T * long(t))$
\newline
Esto es cierto si $t \in temas(s) \wedge (\forall t' \in temas(s)) long(t)
\geq long(t')$
\newline
\newline
Con estas consideraciones, nos queda que la complejidad del algoritmo queda
como:
\newline
\newline
$O(A*long(a) + long(t) + A^2 * T^2 * long(t))$
\newline
Si y solo si $(a \in autores(s) \wedge (\forall a' \in autores(s)), long(a) \geq long(a'))
\wedge (t \in temas(s) \wedge (\forall t' \in autores(t)), long(t) \geq
long(t'))$

\subsection{iDisputarTema}
La complejidad de esta funci\'on va a quedar determinada por el agregado del
significado a un diccionario y la iteraci\'on en la cual elimina los temas que
estan en disputas.
\newline
\newline
Por parte del agregado de un nuevo significado al diccionario, tiene la
siguiente complejidad.
\newline
\newline
$O(long(a) + A * long(t))$
\newline
\newline
Para el proceso de eliminaci\'on de los temas que est\'an en disputas, lo tenemos de
la siguiente forma:
\newline
\newline
$O(\sum_{a \in autores(s)} \sum_{t' \in temas(s)} equals(t, t')) \equiv
O(\sum_{a \in autores(s)} \sum_{t' \in temas(s)} long(t))$\\
$O(A * T * long(t))$
\newline
\newline
Por lo tanto la complejidad nos queda como:
\newline
\newline
$O(long(a) + A * long(t) + A * T * long(t))$

\subsection{iTemas}
En el caso de los temas del sadaic, tiene una complejidad de O(1) ya que es
retornar un iterador.

\subsection{iAutores}
En el caso de los autores del sadaic, tiene una complejidad de O(1) ya que es
retornar un iterador.

\subsection{iTemasDe}
El costo que tiene retornar los temas de un interprete es de O(long(a)) ya que
es el costo que tiene de obtener un significado de un diccionario.

\subsection{iTemasDisputados}
El costo que tiene retornar los temas de un interprete es de O(long(a)) ya que
es el costo que tiene de obtener un significado de un diccionario.

\subsection{iCoAutores}
La complejidad que va a tener la funci\'on de co autores va a quedar determinada
por los dos ciclos que realiza el algoritmo:
\newline
\newline
$O(\sum_{t \in temasDe(s, a)} \sum_{a_{0} \in autores(s)} equals(a, a_{0}) +
\sum_{a' \in autores}equals(a_{0}, a')) \equiv \\
O(\sum_{t \in temasDe(s, a)} \sum_{a_{0} \in autores(s)} long(a) +
\sum_{a' \in autores}long(a')) \equiv \\ O(A * T * (long(a) + \sum_{a' \in
autores} long(a')))$
Si consideramos que tomamos el mas largo de los string de los autores, la
complejidad queda como:
$O(A * T * (long(a) + A * long(a')))$ en donde $a' \in autores(s) \wedge
(\forall a_{0} \in autores(s)) long(a') \geq long(a_{0})$

\subsection{iFTS}
Veamos que sucede con la complejidad de esta funci\'on. Si la clave se encuentra
definida, el costo de la operaci\'on es de O(long(s)). Ya que ingresar a
cualquiera de los dos if me cuesta O(long(s)) y las operaciones que se
encuentran dentro de los cuerpos, no se va fuera del costo de O(long(s))
\newline
\newline
El ``grueso'' de la funci\'on se produce cuando no est\'an definidos y tengo que
realizar la b\'usqueda como si fuera una expresi\'on. Buscar en el diccionario
autorXTemas tiene el siguiente costo:
\newline
\newline
$O(A * long(s) * A * T * long(t))$ En donde $t \in temas(s) \wedge (\forall
t_{0} : temas(s)) long(s) \geq long(t_{0})$
\newline
\newline
Como el agregado, en un principio, se hace de forma r\'apida, no excede m\'as all\'a
de esta complejidad. A esto debemos sumarle el costo de buscarlo dentro de las
claves de temaXAutores y sumarlo al conjunto de soluci\'on:
\newline
\newline
$O(A * long(s) * T * long(t))$ En donde $t \in temas(s) \wedge (\forall
t_{0} : temas(s)) long(s) \geq long(t_{0})$
\newline
\newline
Entonces la complejidad de la funcion nos queda como:
\newline
\newline
$O(A^2 * long(s) * T * long(t) + A * long(s) * T * long(t))$ En donde $t \in temas(s) \wedge (\forall
t_{0} : temas(s)) long(s) \geq long(t_{0})$

\subsection{iDameUnTemaDisputadoPor}
La complejidad de este algoritmo la tenemos definida por el costo que tenemos al
momento de evaluar si el string ingresado es igual al anterior (O(long(s))) y si
el string no es el mismo que el anterior, tenemos que volver a pedir un nuevo
iterador para los nuevos temas, esto tiene un costo de (O(long(s))). Debido a
esto el costo nos queda definido como:
$O(long(s))$

\subsection{iNuevoNodo}
Las operaciones que realiza esta funci\'on, se encuentran dentro de las que tienen
un costo de O(1). Lo unico que puede llegar a pensar que puede alterar la
complejidad haci\'endola lineal es el ciclo que se encuentra en la misma, veamos
que sucede con eso:
\newline
\newline
$O(\sum_{1}^{256} 1)$
\newline
\newline
Como la iteracion se encuentra acotada por un n\'umero, y esta sumatoria no afecta
a la complejidad de lo que se encuentra en el cuerpo podemos pensar a la
sumatoria de la siguiente forma:
\newline
\newline
$256 * O(1)$
\newline
\newline
Aplicarle al complejidad a esto, sigue siendo O(1).

\subsection{iVacio}
Las operaciones que realiza esta funci\'on se encuentran dentro de las que tienen
un costo de O(1). Debido a que iNuevoNodo() tiene un costo de O(1) no altera la
complejidad de la funci\'on.

\subsection{iDefinir}
La complejidad que tiene la funci\'on va a quedar determinada en funci\'on del
costo que tenemos en la iteraci\'on y el agregado de un elemento m\'as al con-
junto de significados dentro del diccionario. Adem\'as de esto, debe tenerse en
cuenta que como la clave se pasa por copia, tambi\'en debe agregarse al costo.
\newline
\newline
El agregado hacia el conjunto de claves lo hace mediante el agregado r\'apido cuyo
costo es equivalente al costo de copiar el elemento. En ese caso la expresi\'on
queda como:
\newline
\newline
$O(copy(c)) \equiv O(long(c))$
\newline
\newline
Por otro lado, analizando el ciclo, tenemos que en cada ejecuci\'on se realizan
operaciones cuyo costo es O(1). Entonces la cantidad de iteraciones va a ser
proporcional a la cantidad de letras que tiene el string. En ese caso la
expresion nos queda como:
\newline
\newline
$O(\sum_{l \in c} 1) \equiv O(long(c))$
\newline
\newline
Adem\'as, la funci\'on copia la clave, lo cual su costo es proporcional a la
cantidad de letras que contenga el string, ya que son las que deben copiarse. En
si la complejidad de la funci\'on queda definida como:
\newline
\newline
$O(long(c) + long(c) + long(c)) \equiv O(3 * long(c)) \equiv O(long(c))$

\subsection{iAgregarSignificado}
La complejidad que tiene la funci\'on va a quedar determinada en funci\'on del costo
que tenemos al iterar el ciclo y el agregado de un elemento m\'as al conjunto de
significados dentro del diccionario.
\newline
\newline
En el cuerpo de la iteraci\'on, solamente tenemos operaciones que tiene una
complejidad de O(1), por lo tanto la iteraci\'on queda ligada a la cantidad de
letras que tiene el string:
\newline
\newline
$O(\sum_{a \in c}) * O(1) \equiv O(long(c)) * O(1) \equiv O(long(c))$
\newline
\newline
El agregado a un elemento m\'as a los significados, se realiza mediante el
agregado r\'apido ya que el elemento no esta definido en el conjunto, debido a
ello la complejidad queda como la siguiente:
\newline
\newline
$O(long(s))$
\newline
\newline
Con esto la complejidad que nos queda es la siguiente:
\newline
\newline
$O(long(c) + long(s))$

\subsection{iDef?}
La complejidad que tiene la funci\'on va a quedar determinada en funci\'on del costo
que tenemos al iterar el ciclo:
\newline
\newline
En el cuerpo de la iteraci\'on, solamente tenemos operaciones que tiene una
complejidad de O(1), por lo tanto la iteraci\'on queda ligada a la cantidad de
letras que tiene el string:
\newline
\newline
$O(\sum_{a \in c}) * O(1) \equiv O(long(c)) * O(1) \equiv O(long(c))$
\newline
\newline
El resultado esta devuelto en operaciones que quedan acotadas como O(1), por lo
tanto la complejidad que nos queda es la siguiente:
\newline
\newline
O(long(c))

\subsection{iClaves}
La funci\'on solamente retora un iterador de las claves que tiene definida, por lo
tanto el costo que tiene es de O(1).

\subsection{iObtener}
La complejidad que tiene la funci\'on va a quedar determinada en funci\'on del costo
que tenemos al iterar el ciclo.
\newline
\newline
En el cuerpo de la iteraci\'on, solamente tenemos operaciones que tiene una
complejidad de O(1), por lo tanto la iteraci\'on queda ligada a la cantidad de
letras que tiene el string:
\newline
\newline
$O(\sum_{a \in c}) * O(1) \equiv O(long(c)) * O(1) \equiv O(long(c))$
\newline
\newline
El resultado esta devuelto en operaciones que quedan acotadas como O(1), por lo
tanto la complejidad que nos queda es la siguiente:
\newline
\newline
O(long(c))

\subsection{iObtenerSignificados}
La complejidad que tiene esta funci\'on va a quedar determinada por el costo que
tenemos de la iteraci\'on de tres ciclos.
\newline
\newline
Para analizara la complejidad, vamos a pensar a los tres ciclos de la siguiente
manera:
\newline
\newline
$O(\sum_{d \in clavesCoincidentes(c, claves(s))} \sum_{s \in significados(s, d)}
\sum_{s_{0} \in significados} equals(s, s_{0}))$
\newline
\newline
Es decir, para cada clave coincidente, tomo sus significados y los agrego en el
resultado, que ya que no se puede hacer de forma r\'apida, tengo que volver a
chequearlo para ver que no estoy ingresando repetidos. Veamos que podemos hacer
con cada una de las expresiones:
\newline
\newline
Por parte de las claves coincidentes, puedo suponer que en el peor de los casos,
coinciden todas las claves. Pero caer\'ia en un error, ya que las claves
coincidentes tienen su propia complejidad que es distinta a de ``pensar'' que
tengo todas las claves a mi merced. Lo que s\'i puedo pensar es que al momento de
verificar si dos significados son iguales, tiene un costo proporcional a
la longitud de alguno de los dos string, entonces la expresi\'on queda como:
\newline
\newline
$O(\sum_{d \in clavesCoincidentes(c, claves(s))} \sum_{s \in significados(s, d)}
\sum_{s_{0} \in significados} long(s_{0}))$
\newline
\newline
Ahora trabajemos sobre la expresion actual:
\newline
\newline
$O(\sum_{d \in clavesCoincidentes(c, claves(s))} \sum_{s \in significados(s, d)}
\sum_{s_{0} \in significados} long(s_{0})) \equiv$
\\ \\
$O(\# clavesCoincidentes(c, claves(s) * \# significados(s)
* \sum_{s_{0} \in significados} long(s_{0})) \equiv$
\\ \\
$O(\# claves(s) * long(c) * \# claves(s) * \sum_{s \in significados(s)}
long(s))$
\newline
\newline
Aclaracion, podemos hacer pensar que $\# significados(s) \equiv \#
claves(s)$ ya que por la naturaleza del diccionario existe la misma cantidad de
significados como claves. De la complejidad que quedo se puede pensar tambi\'en
una mejor cota:
\newline
\newline
$O(\sum_{s \in significados} long(s)) \equiv O(\#significados * long(s))$
\newline
Esto es cierto si y solo si $s \in significados(s) \wedge (\forall s_{0} \in
significados(s)) long(s) \geq long(s_{0})$
\newline
\newline
Por lo tanto la complejidad nos queda como:
\newline
\newline
$O(\# claves(s) * long(c) * \# claves(s) * \# significados(s) * long(s))$
\newline
Esto es cierto si y solo si $s \in significados(s) \wedge (\forall s_{0} \in
significados(s)) long(s) \geq long(s_{0})$

\subsection{iClavesCoincidentes}
La complejidad que tiene la funci\'on va a quedar determinada en funci\'on del costo
que tenemos al iterar el ciclo.
\newline
\newline
En el cuerpo de la iteraci\'on, tenemos dos funciones que generan ``peso'': por un
lado tenemos que ver si un string coincide con otro y por otro lado tenemos el
agregado de un elemento a un conjunto. Como los agregados que tenemos no
contienen elementos repetidos, utilizamos la funci\'on de AgregadoRapido que tiene
un costo de O(1), por lo tanto el cuerpo del ciclo queda definido, en t\'erminos
de complejidad, por lo que sucede con la coincidencia:
\newline
\newline
$O(\sum_{d \in ds} coincide(c, d)) \equiv O(\sum_{d \in ds} long(c)) \equiv
O(\#ds * long(c))$

\subsection{iCoincide}
Si el prefijo que queremos ver si coincide es mayor a la palabra que queremos
comparar determinamos que no coincide, por lo tanto la complejidad va a quedar
atada a lo que sucede cuando tenemos que iterar en en el string que queremos
verificar si coincide o no:
\newline
\newline
$O(\sum_{a \in d}) * O(1) \equiv O(long(d)) * O(1) \equiv O(long(d))$


\end{document}